package 二分法;

public class findMedianSortedArrays4 {
    /**
     * 方法一：使用归并的方式，合并两个有序数组，得到一个大的有序数组。大的有序数组的中间位置的元素，即为中位数。
     * <p>
     * 方法二：不需要合并两个有序数组，只要找到中位数的位置即可。由于两个数组的长度已知，因此中位数对应的两个数组的下标之和也是已知的。
     * 维护两个指针，初始时分别指向两个数组的下标 0的位置，每次将指向较小值的指针后移一位（如果一个指针已经到达数组末尾，则只需要移动另一个数组的指针），直到到达中位数的位置。
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] array = new int[nums1.length + nums2.length];
        int index = 0;
        int left = 0;
        int right = 0;
        while (left < nums1.length && right < nums2.length) {
            if (nums1[left] >= nums2[right]) {
                array[index++] = nums2[right++];
            } else {
                array[index++] = nums1[left++];
            }
        }
        while (left < nums1.length) {
            array[index++] = nums1[left++];
        }
        while (right < nums2.length) {
            array[index++] = nums2[right++];
        }
        if (array.length % 2 == 0) {
            return ((array[array.length / 2] + array[array.length / 2 - 1]) * 1.0) / 2;
        } else {
            return (array[array.length / 2]);
        }
    }
}
